#include "PathCreator.h"


/*The algorithm for maze generation is as follows:

* Generate a random ordering of the edges (or, as you experiment with extensions, some other ordering that produces "better" mazes)
* Generate a set of single-node trees, one for each room
* While there is more than one tree in the forest, do:
o Consider the next edge in the ordering
o If the two rooms it borders are already in the same set, ignore it
o Otherwise remove this edge (i.e., mark it as an open edge and not a wall) and union the two trees containing these two rooms
*/

PathCreator::PathCreator (int width, int height, vector<Triangle*> triangles){
	/*In the constructor, PathCreator get a set of non-duplicate edges by going through all the triangles
	 */
    this->width = width;
    this->height = height;
	disjointSets = new DisjointSets;
	int numberOfTriangles = triangles.size();
	for (int i = 0; i < numberOfTriangles; i++){
		Triangle* t = triangles.at(i);

		/*first, put the triangle in the disjoin union set
		this is to prepare for finding the path between the triangles
		 */
		disjointSets->addElement(t);

		/*Now it's just a matter of going through each triangle,
		 and try to add all three of its sides.
		 However, we do need to avoid duplicate edges,
		 which is why we are using a set
		 */
		pair<set<Edge*, EdgeCompare>::iterator,bool> ret;

		Edge* e = new Edge(t->getPoint1(), t->getPoint2(), t, t->getNeighbourBetween12());
		ret = edgeSet.insert(e);

		//If the edge is already in the set, it's useless, delete it
		if (!ret.second){
			delete e;
		}

		e = new Edge(t->getPoint2(), t->getPoint3(), t, t->getNeighbourBetween23());
		ret = edgeSet.insert(e);
		if (!ret.second){
			delete e;
		}

		e = new Edge(t->getPoint3(), t->getPoint1(), t, t->getNeighbourBetween31());
		ret = edgeSet.insert(e);
		if (!ret.second){
			delete e;
		}
	}
}

PathCreator::~PathCreator(){
	delete disjointSets;
}

vector<Edge*> PathCreator::getEdges(){
	vector<Edge*> edges = randomize();
	knockDownWalls(edges);
	return edges;
}

/*This function randomizes the set of edges and put them in a vector
 */
vector<Edge*> PathCreator::randomize(){
	vector<Edge*> edges;
	set<Edge*, EdgeCompare>::iterator it;
        Edge * anEdge;

	//first, put the edges into a vector
	for (it = edgeSet.begin(); it!=edgeSet.end(); it++) {
                anEdge = *it;
                edges.push_back(anEdge);
	}

	/*The algortherim for randomzing the edges
	 For each edges, that that edge, and swap it with a random edge that's positioned after it

	*/
	int numberOfEdges = edges.size();
	for (int i = 0; i < numberOfEdges; i++){
		int swapWithIndex = i+(rand() % (edges.size()-i));
		Edge* temp = edges.at(i);
		edges.at(i) = edges.at(swapWithIndex);
		edges.at(swapWithIndex) = temp;
	}

	return edges;
}

/*This method finally does the creating path part

 To make sure that each triangle in the maze has only one path to any other given triangle, we use disjoin union set

 */
void PathCreator::knockDownWalls(vector<Edge*>& edges){
	int numberOfEdges = edges.size();
	for (int i = 0; i < numberOfEdges; i++){
		Edge* e = edges.at(i);
		//We shouldn't have gotten any null edges,
		//but it would be so embarrassing if it happens on the off-chance in the demo
		if (e == NULL){
			continue;
		}

		//Get the two triangles in question
		Triangle* t1 = e->getTriangle1();
		Triangle* t2 = e->getTriangle2();

		//again, check for NULL just in case
		if (t1 != NULL && t2!=NULL){
			//is there a path between these two triangles?
			if (disjointSets->findSet(t1) != disjointSets->findSet(t2)){
				//not in the same set, break down wall and perform union
                                e->status = Edge::OPEN;
				disjointSets->unionSets(t1, t2);
			}
		}
	}
}
